package tree.easy;

import tree.TreeNode;

/**
 * 993. 二叉树的堂兄弟节点
 */
public class isCousins {

    int parentNodeX = -1;
    int parentNodeY = -1;
    int deepX = 0;
    int deepY = 0;
    public boolean isCousins(TreeNode root, int x, int y) {
        dfs(root, x, y, 0);
        if (parentNodeX < 0 || parentNodeY < 0) {
            return false;
        }
        return parentNodeX != parentNodeY && deepX == deepY;
    }

    public void dfs(TreeNode root, int x, int y, int deep) {
        if (root != null) {
            if (root.right == null && root.left == null) {
                return;
            }
            if (root.left != null) {
                if (root.left.left != null || root.left.right != null) {
                    dfs(root.left, x, y, deep + 1);
                }
                if (root.left.val == x) {
                    deepX = deep;
                    parentNodeX = root.val;
                } else if (root.left.val == y) {
                    deepY = deep;
                    parentNodeY = root.val;
                }
            }
            if (root.right != null) {
                if (root.right.right != null || root.right.left != null) {
                    dfs(root.right, x, y, deep + 1);
                }
                if (root.right.val == x) {
                    deepX = deep;
                    parentNodeX = root.val;
                } else if (root.right.val == y) {
                    deepY = deep;
                    parentNodeY = root.val;
                }
            }
        }
    }
}
